package sword.T31;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: duyuzhou
 * @Create: 2022-04-07 15:56:38 星期四
 */
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int p = 0, q = 0, n = pushed.length;
        Deque<Integer> stack = new LinkedList<>();
        while (p < n && q < n) {
            while (stack.isEmpty() || stack.peek() != popped[q]) {
                stack.push(pushed[p++]);
                if (p >= n)
                    break;
            }
            while (!stack.isEmpty() && stack.peek() == popped[q]) {
                stack.pop();
                q++;
            }
        }
        return q == n;
    }
}
